package LearnAlgorithm.f_字符串;

import java.util.Arrays;

public class n字符串匹配SuffixArrayNotStaticPlus倍增法改进 {
	public static void main(String[] args) {
		String mother = "ABABABABB";
        String child = "BABB";
        new n字符串匹配SuffixArrayNotStaticPlus倍增法改进().suffixArrayMatchUpdate(mother, child);
//        new n字符串匹配SuffixArrayNotStaticPlus倍增法().suffixArrayMatch(mother, child);
	}
	
	/**
	 * O(N*logN*logN + N*logM)
	 * @param mother
	 * @param child
	 */
	public void suffixArrayMatchUpdate(String mother, String child) {
		Suff[] suffixArray = makeSuffixArrayUpdate(mother);
		int l = 0;
		int r = mother.length() - 1;
		while (r >= l) {
			int mid = l + ((r - l) >>> 1);
			int compareResult = 0;
			String suffMid = mother.substring(suffixArray[mid].getIndex(), r + 1);//仅仅这里不一样；这里通过index变量去获取指定的字符片段；指定的字符片段就是suffixArray逻辑上的“中值字符片段”
			if (suffMid.length() >= child.length()) {
				compareResult = suffMid.substring(0, child.length()).compareTo(child);
			} else {
				compareResult = suffMid.compareTo(child);
			}
			if (compareResult == 0) {
				System.out.println("index:" + suffixArray[mid].getIndex());
				return;
			} else if (compareResult < 0) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		System.out.println("没找到,输出所有的后缀数组：");
		printSuffixArray(suffixArray);
	}
	
	/**
	 * O(N*logN*logN)
	 * @param string
	 * @return
	 */
	public Suff[] makeSuffixArrayUpdate(String string) {
		int length = string.length();
		int[] rk = new int[length];
		Suff[] suffixArray = new Suff[length];
		for (int i = 0; i < length; i++) {//suffixArray的string只被存储一次；存储单个字符；下面的倍增法处理过程，不会更新suffixArray[i]的string变量；将来的自己听着，你可以理解为“逻辑上更新了，但是物理上没更新”；因为每个suffixArray[i]的rk[]值一直在更新
			suffixArray[i] = new Suff(string.charAt(i) + "", i);
		}
		Arrays.sort(suffixArray);//O(NlogN)	排序suffixArray
		//第1次更新每个suffixArray[i]的rk[]值
		rk[suffixArray[0].getIndex()] = 1;//默认rk[]值 = 1；从1开始是为了最后跟新的rk[string.length-1] = string.length；好让增量法跳出循环
		for (int i = 1; i < length; i++) {//已排序suffixArray，前一位A的rk[]赋值给后一位B
			rk[suffixArray[i].getIndex()] = rk[suffixArray[i - 1].getIndex()];
			//判断string相等？不等的话B的rk[]++；这种赋值方式是为了使“string相等”的两suffixArray元素的rk[]值一样
			if (!suffixArray[i].getString().equals(suffixArray[i - 1].getString())) {//这里的比较是物理比较
				rk[suffixArray[i].getIndex()]++;
			}
		}
		//下面开始倍增法Update
		//下面的倍增法处理过程，不会更新suffixArray[i]的string变量；
		//将来的自己听着，你可以理解为“逻辑上更新了，但是物理上没更新”；
		//因为每个suffixArray[i]的rk[]值一直在更新
		/*
		退出的条件rk[suffixArray[length - 1].getIndex()] < length
		意思是最后终于排好序的suffixArray的最后一个元素的index变量(假设为valueIndex)，
		以这个变量为索引，最后一次更新后的rk[valueIndex]的值(假设为location),
		location如果 >= string.length,跳出循环
		
		事实上最后终于排好序的suffixArray的最后一个元素的index变量数值上 = string.length-1
		而且根据rk[]的性质，最后一次更新后的rk[string.length-1]就等于 string.length
		所以跳出循环，因为我们rk[]默认值从1开始
		 */
		for (int k = 2; rk[suffixArray[length - 1].getIndex()] < length; k *= 2) {
			final int kk = k;
			Arrays.sort(suffixArray, (o1, o2) -> {//自定义排序规则
				int x = ((Suff) o1).getIndex();
				int y = ((Suff) o2).getIndex();
				if (rk[x] == rk[y]) {
					if (x + kk / 2 >= length || y + kk / 2 >= length) {//新的方式处理“第二种不够长”；最终结果仍然是“谁字符片段长谁在后面”
						//o1如果比o2靠前；数值上x < y；-(x-y)是正数；o1会被存入o2的后面
						//o1如果比o2靠后；数值上x > y；-(x-y)是负数；o1会被存入o2的前面
						return -(x - y);
					}
					return rk[x + kk / 2] - rk[y + kk / 2];
				} else {
					return rk[x] - rk[y];
				}
			});
			//更新每个suffixArray[i]的rk[]值;
			//不更新suffixArray[i]的string变量
			rk[suffixArray[0].getIndex()] = 1;//默认rk[]值 = 1；从1开始是为了最后跟新的rk[string.length-1] = string.length；好让增量法跳出循环
			for (int i = 1; i < length; i++) {
				int i1 = suffixArray[i].getIndex();//后一位元素
				int i2 = suffixArray[i - 1].getIndex();//前一位元素
				rk[i1] = rk[i2];//已排序suffixArray，前一位A的rk[]赋值给后一位B
				try {
					//判断string相等？不等的话B的rk[]++；这种赋值方式是为了使“string相等”的两suffixArray元素的rk[]值一样
					//这里的比较是逻辑比较；可以看到substring(i1, i1 + kk)这样来产生“用于比较的字符片段”
					/*
					这里逻辑比较很巧妙：
						把逻辑上string变量不相等的
							就看if判断；判断通过就++，没通过就不变(因为是rk[i1] = rk[i2]这样赋值的)
						把逻辑上string变量“长度”不等的
							就看catch处理；处理方法一律将后一位元素(rk[i1])进行++；为什么可以无脑一律?因为在排序好的suffixArray中，你TM“逻辑string变量”都长度不一样了，还有可能相等么？
					都考虑到了
					 */
					if (!string.substring(i1, i1 + kk).equals(string.substring(i2, i2 + kk))) {//这里的比较是逻辑比较
						rk[i1]++;
					}
				} catch (Exception e) {
					rk[i1]++;//非常巧妙
				}
			}
		}
		return suffixArray;//返回的suffixArray中有用的其实是suffixArray[i].getIndex()
	}
	
	public void suffixArrayMatch(String mother, String child) {
		Suff[] suffixArray = makeSuffixArray(mother);//O(N*logN*logN)
		int l = 0;
		int r = mother.length() - 1;
		while (r >= l) { 
			int mid = l + ((r - l) >>> 1);
			int compareResult = 0;
			String suffMid = suffixArray[mid].getString();
			if (suffMid.length() >= child.length()) {
				compareResult = suffMid.substring(0, child.length()).compareTo(child);
			} else {
				compareResult = suffMid.compareTo(child);
			}
			if (compareResult == 0) {
				System.out.println("index:" + suffixArray[mid].getIndex());
				return;
			} else if (compareResult < 0) {
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		System.out.println("没找到,输出所有的后缀数组：");
		printSuffixArray(suffixArray);
	}
	
	public Suff[] makeSuffixArray(String string) {
		int length = string.length();
		int[] rk = new int[length];
		Suff[] suffixArray = new Suff[length];
		for (int k = 1; k <= length; k *= 2) {
			for (int i = 0; i < length; i++) {
				suffixArray[i] = new Suff(string.substring(i, i + k > length ? length : i + k), i);
			}
			if (k == 1) {
				Arrays.sort(suffixArray);
			} else {
				final int kk = k;
				Arrays.sort(suffixArray, (o1, o2) -> {
					int x = ((Suff) o1).getIndex();
					int y = ((Suff) o2).getIndex();
					if (rk[x] == rk[y]) {
						try {
							return rk[x + kk / 2] - rk[y + kk / 2];
						} catch (Exception e) {
							return o1.getString().length() - o2.getString().length();
						}
					} else {
						return rk[x] - rk[y];
					}
				});
			}
			int r = 0; 
			rk[suffixArray[0].getIndex()] = r; 
			for (int i = 1; i < length; i++) { 
				if (suffixArray[i].compareTo(suffixArray[i - 1]) == 0) { 
					rk[suffixArray[i].getIndex()] = r; 
				} else {
					rk[suffixArray[i].getIndex()] = ++r; 
				}
			}
		}
		return suffixArray;
	}
	
	public void printSuffixArray(Suff[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.println(arr[i]);
		}
	}
	
	public class Suff implements Comparable<Suff> {
		private String string = null;
		private int index = 0;
		public Suff() {};
		public Suff(String string, int index) {
			this.string = string;
			this.index = index;
		}
		public void setString(String string) {
			this.string = string;
		}
		public String getString() {
			return this.string;
		}
		public void setIndex(int index) {
			this.index = index;
		}
		public int getIndex() {
			return this.index;
		}
		@Override
		public int compareTo(Suff other) {
			return this.string.compareTo(other.string);
		}	
		@Override
        public String toString() {
            return "Suff {" +
                    "string='" + string + '\'' +
                    ", index=" + index +
                    '}';
        }
	}
}
